package homework_2020_03_29;
/**401. 二进制手表
 * 二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
 *
 * 每个 LED 代表一个 0 或 1，最低位在右侧。
 *
 * 例如，上面的二进制手表读取 “3:25”。
 *
 * 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
 *
 * 案例:
 *
 * 输入: n = 1
 * 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
 *  
 *
 * 注意事项:
 *
 * 输出的顺序没有要求。
 * 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
 * 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-watch
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


import java.util.ArrayList;
import java.util.List;

public class leetcode_401 {
    public static void main(String[] args) {
        Solution_401 s = new Solution_401();
        int num = 1;
        List<String > list = s.readBinaryWatch(num);
        for(String st:list) {
            System.out.println(st);
        }
    }

}
class Solution_401 {
    List<String> res = new ArrayList<String>();
    //记录手表位置
    int[] watch = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
    //记录是否亮灯
    int[] onOff = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    public List<String> readBinaryWatch(int num)
    {
        //不存在同时亮8盏灯以上的情况
        if(num > 8) return res;
        dfs(num, 0, 0);
        return res;
    }

    /**
     * 深度遍历
     * @param num 要求亮灯的数
     * @param onSum 已亮灯数
     * @param start 从第几个灯开始亮
     */
    public void dfs(int num, int onSum ,int start)
    {
        //如果亮的数量等于要求数量，加进list
        if(onSum == num)
        {
            addResult();
            return;
        }

        for(int i = start; i < watch.length; i++)
        {
            //这个灯亮
            onOff[i] = 1;
            dfs(num, onSum + 1, i + 1);
            //这个灯不亮
            onOff[i] = 0;
        }
    }

    public void addResult()
    {
        int hour = 0;
        int minute = 0;
        for(int i = 0; i < onOff.length; i++)
        {
            //如果这个灯是亮的
            if(onOff[i] == 1)
            {
                //小于4是时，大于等于是分
                if(i < 4)
                {
                    hour += watch[i];
                }
                else
                {
                    minute += watch[i];
                }
            }
        }
        //排除规则外情况
        if(hour > 11 || minute > 59) return;
        String time = hour + ":" + ((minute < 10) ? "0"+minute : minute);
        res.add(time);
    }
}